package lib

import(
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         234,
		Discription: "回文链表",
		Level:       2,
		Labels: map[string]int{
			"快慢指针":  1,
			"头插": 1,
		},
	})
}

func IsPalindrome3(head *ds.ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}

	fast := head
	slow := head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}

	//此时slow可能指向的是中间的节点（奇数），也可能指向的是下半个链表的头节点（偶数）
	//两种情况对于回文都一样
	newHead := slow
	cur := newHead.Next
	newHead.Next = nil
	for cur != nil {
		next := cur.Next
		cur.Next = newHead
		newHead = cur
		cur = next
	}

	for newHead != nil && head != nil {
		if newHead.Val != head.Val {
			return false
		}
		newHead = newHead.Next
		head = head.Next
	}

	return true
}